package homework;

import java.util.*;

public class HomwWork44 {
    //前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer>list=new ArrayList<>();
        Stack<TreeNode>stack=new Stack<>();
        stack.add(root);
        while (!stack.empty()){
            TreeNode cur=stack.pop();
            list.add(cur.val);
            if (cur.right!=null) stack.add(cur.right);
            if(cur.left!=null) stack.add(cur.left);
        }
        return list;
    }
    //中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer>list=new ArrayList<>();
        if(root==null){
            return list;
        }
        Stack<TreeNode>stack=new Stack<>();
        while (root!=null||!stack.isEmpty()){
            while (root!=null){
                stack.add(root);
                root=root.left;
            }
            root=stack.pop();
            list.add(root.val);
            root=root.right;
        }
        return list;
    }
    //后续遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer>list=new LinkedList<>();
        if(root==null){
            return list;
        }
        TreeNode cur=null;
//        Deque <TreeNode> deque=new LinkedList<>();

//        deque.addFirst(root);
//        while (!deque.isEmpty()){
//            cur=deque.removeFirst();
//            list.addFirst(cur.val);
//            if(cur.left!=null){
//                deque.addFirst(cur.left);
//            }
//            if(cur.right!=null){
//                deque.addFirst(cur.right);
//            }
        Stack<TreeNode>stack=new Stack<>();
        stack.add(root);
        while (!stack.empty()){
            cur=stack.pop();
            list.addFirst(cur.val);
            if(cur.left!=null){
                stack.add(cur.left);
            }
            if(cur.right!=null){
                stack.add(cur.right);
            }
        }
        return list;
    }
}
